ApSimon’s Mints
Hugh ApSimon described the following coin puzzle in his book Mathematical Byways in Ayling, Beeling and Ceiling
New coins are being minted at n independent mints. There is a suspicion that some mints might use a variant material for the coins. There can only be one variant material: fake coins weigh the same independently of the mint. The weight of genuine coins is known, but the weight of fake coins is not. There is a machine that can precisely weigh any number of coins, but the machine can only be used twice. You can request several coins from each mint and then perform the two weighings so that you can deduce with certainty which mints produce fake coins and which mints produce real coins. What is the minimum total of coins you need to request from the mints?
I will follow ApSimon’s notation. Suppose Pr and Qr is the number of coins from the mint r used in the first and the second weighing correspondingly. That is, we are minimizing Σmax(Pr,Qr). (All my summations are over all the mints. I skip the summation limits because it is difficult to write math in html.) Let us denote by W the weight of the genuine coin and by W(1 + ε) the weight of the fake coin. We do not know ε, except that it is not zero.
Let dr be either 0 or 1, depending on what material the r-th mint uses. Thus, the coin from the r-th mint weighs W(1 + drε). We know the results of these two weighings and the weight of the genuine coin. Therefore, we can calculate the following two values: a = ΣPrdrε and b = ΣQrdrε.
It is clear that we need to request at least one coin from each mint and use it in at least one weighing: Pr + Qr > 0. If both sums a and b are zero, then all the mints are producing genuine coins. Neither of the two values gives us much information as we do not know ε. We can get rid of ε by dividing a by b.
There are 2n − 1 combinations of possible answers: these are subsets of the set of mints producing fake coins given that there is at least one. Thus we need to select numbers Pr and Qr, so that a/b produces 2n − 1 possible answers for different sets of values of dr.
Let us consider cases in which the total number of mints is small. If there is one mint we can take one coin and we won’t even need a second weighing. For two mints we need one coin from each mint for a total of 2. For three mints, one coin from each mint is not enough. I leave this statement as an exercise. It is possible to test three mints with four coins: one each from the first and second mints and two from the third mint. The coins from each mint for the first and second weighings are (0,1,2) and (1,1,0) respectively.
To prove that this works we need to calculate (d2 + 2d3)/(d1 + d2) for seven different combinations of dr. I leave this as an exercise.
This puzzle seems to be very difficult. We only know the answer if the number of mints is not more than seven. The corresponding sequence A007673 in the OEIS is: 1, 2, 4, 8, 15, 38, 74. It is possible to give bounds for this sequence, but they are so far apart. The lower bound is n. And the ApSimon’s book offers a construction for two weighings were Pr = r! and Qr = 1.
You can try to find a better construction, or you can try calculating more terms of the sequence. You can also read more about this problem in my short paper Attacking ApSimon’s Mints.
I do not want to leave the readers with the puzzle that might end up being intractable. So I suggest the following easy puzzle. Solve the ApSimon’s Mints problem assuming that the weight of the fake coin is known.
Share:
David Reynolds:
I believe that there’s a simpler solution.
Use one coin from each mint in the first weighing.
This yields the weight of a fake coin as well as the number of mints minting fake coins.
For the second weighing, use one coin from mint 1, two coins from mint 2, four coins from mint 3, … 2^n coins for mint n.
Let Ng = number of genuine coins.
Let Nf = number of fake coins.
Let Wt = total weight of second weighing.
Since we know W and W(1+e), we have two equations.
Eq 1. Ng * W + Nf * W(1+e) = Wt
Eq 2. Ng + Nf = 2^(n+1)-1
Equation 1 by itself could possibly be ambiguous. But both equations allow us to uniquely solve for Nf in the second weighing.
Express Nf as a binary value and the ‘1’ bits represent the mints that are minting fake coins.
Note that the number of ‘1’ bits must equal the number of mints minting fake coins that we determined in the first weighing.
This allows us to optimize further and not add any coins for the last mint.
After determining the number of ‘1’ bits, then we can know whether the last mint was minting genuine or fake coins.
So, my solution is
Pr = 1
Qr = 2^(r-1) (except Qn = 0)
My sequence of total coins is 1, 2, 4, 8, 16, 32, 64, … 2^n.
14 June 2014, 3:54 pmMy solution for 5 mints is not optimal, but beyond that, my progression is better.
David Reynolds:
oops, minor typo.
14 June 2014, 3:58 pmThe final statement should be:
My sequence of total coins is 1, 2, 4, 8, 16, 32, 64, … 2^(n-1).
David Reynolds:
Oh wow. Disregard my postings. I just realized that my first assertion was wrong, leading to totally wrong results. D’oh. Not feeling real good right now.
14 June 2014, 4:54 pmDavid Reynolds:
If the weight of the fake coin is known, then my postings are valid. I think I got confused about the problem I was trying to solve. Still feeling like an idiot. 8-(
14 June 2014, 5:07 pmDavid Reynolds:
In the case where the weight of the fake coins is known.
It is possible to determine the fraudulent mints in just one weighing.
1 coin from mint 1, 2 coins from mint 2, 4 coins from mint 3, … 2^(n-1) coins for mint n.
The weight discrepancy will tell us how many coins are fake and from that we can determine the mints responsible.
In two weighings, I do not see a method that improves on dividing the mints in half and testing each group disjointedly.
In the case where the weight of the fake coins is not known, I’ll offer my original posting restated.
First weighing: 1 coin from each mint.
Record the weight discrepancy. It doesn’t tell us anything, except in the case where the discrepancy is zero.
Second weighing:
1 coin from mint 1, 2 coins from mint 2, 4 coins from mint 3, … 2^(n-1) coins for mint n.
Again, check the weight discrepancy.
If it is unchanged, only mint 1 is fraudulent.
If it is doubled, only mint 2 is fraudulent.
If it is increased four fold, only mint 3 is fraudulent.
etc.
If it is multiplied by 5, both mints 1 and 4 are fraudulent.
It can easily be seen that the increase will be integral and the binary decomposition will uniquely yield the fraudulent mints.
The solution is not optimal. I only offer it as a general upper bound.
1, 3, 7, 15, … 2^n-1
15 June 2014, 12:59 amDavid Reynolds:
Oh bloody hell! I’ve blown it again. Disregard everything I’ve said.
15 June 2014, 1:49 amKonstantin:
I think, 38 and 74 aren’t optimal. So, they are must be excluded from OEIS A007673. My counterexample for n=6 is
18 June 2014, 7:36 amP=(0,1,1,2,4,8) and Q=(9,6,1,1,1,1) -> sum = 9+6+1+2+4+8=30.
Can you check this my result?
Tanya Khovanova:
Konstantin, Fantastic!
It works. Here are the ratios per set: {{{0, 0, 0, 0, 0, 1}, 8}, {{0, 0, 0, 0, 1, 0}, 4}, {{0, 0, 0, 0, 1, 1}, 6}, {{0, 0, 0, 1, 0, 0}, 2}, {{0, 0, 0, 1, 0, 1}, 5}, {{0, 0, 0, 1, 1, 0}, 3}, {{0, 0, 0, 1, 1, 1}, 14/3}, {{0, 0, 1, 0, 0, 0}, 1}, {{0, 0, 1, 0, 0, 1}, 9/2}, {{0, 0, 1, 0, 1, 0}, 5/2}, {{0, 0, 1, 0, 1, 1}, 13/3}, {{0, 0, 1, 1, 0, 0}, 3/2}, {{0, 0, 1, 1, 0, 1}, 11/3}, {{0, 0, 1, 1, 1, 0}, 7/3}, {{0, 0, 1, 1, 1, 1}, 15/4}, {{0, 1, 0, 0, 0, 0}, 1/6}, {{0, 1, 0, 0, 0, 1}, 9/7}, {{0, 1, 0, 0, 1, 0}, 5/7}, {{0, 1, 0, 0, 1, 1}, 13/8}, {{0, 1, 0, 1, 0, 0}, 3/7}, {{0, 1, 0, 1, 0, 1}, 11/8}, {{0, 1, 0, 1, 1, 0}, 7/8}, {{0, 1, 0, 1, 1, 1}, 5/3}, {{0, 1, 1, 0, 0, 0}, 2/7}, {{0, 1, 1, 0, 0, 1}, 5/4}, {{0, 1, 1, 0, 1, 0}, 3/4}, {{0, 1, 1, 0, 1, 1}, 14/9}, {{0, 1, 1, 1, 0, 0}, 1/2}, {{0, 1, 1, 1, 0, 1}, 4/3}, {{0, 1, 1, 1, 1, 0}, 8/9}, {{0, 1, 1, 1, 1, 1}, 8/5}, {{1, 0, 0, 0, 0, 0}, 0}, {{1, 0, 0, 0, 0, 1}, 4/5}, {{1, 0, 0, 0, 1, 0}, 2/5}, {{1, 0, 0, 0, 1, 1}, 12/11}, {{1, 0, 0, 1, 0, 0}, 1/5}, {{1, 0, 0, 1, 0, 1}, 10/11}, {{1, 0, 0, 1, 1, 0}, 6/11}, {{1, 0, 0, 1, 1, 1}, 7/6}, {{1, 0, 1, 0, 0, 0}, 1/10}, {{1, 0, 1, 0, 0, 1}, 9/11}, {{1, 0, 1, 0, 1, 0}, 5/11}, {{1, 0, 1, 0, 1, 1}, 13/12}, {{1, 0, 1, 1, 0, 0}, 3/11}, {{1, 0, 1, 1, 0, 1}, 11/12}, {{1, 0, 1, 1, 1, 0}, 7/12}, {{1, 0, 1, 1, 1, 1}, 15/13}, {{1, 1, 0, 0, 0, 0}, 1/15}, {{1, 1, 0, 0, 0, 1}, 9/16}, {{1, 1, 0, 0, 1, 0}, 5/16}, {{1, 1, 0, 0, 1, 1}, 13/17}, {{1, 1, 0, 1, 0, 0}, 3/16}, {{1, 1, 0, 1, 0, 1}, 11/17}, {{1, 1, 0, 1, 1, 0}, 7/17}, {{1, 1, 0, 1, 1, 1}, 5/6}, {{1, 1, 1, 0, 0, 0}, 1/8}, {{1, 1, 1, 0, 0, 1}, 10/17}, {{1, 1, 1, 0, 1, 0}, 6/17}, {{1, 1, 1, 0, 1, 1}, 7/9}, {{1, 1, 1, 1, 0, 0}, 4/17}, {{1, 1, 1, 1, 0, 1}, 2/3}, {{1, 1, 1, 1, 1, 0}, 4/9}, {{1, 1, 1, 1, 1, 1}, 16/19}}
Sorted ratios are all different:
18 June 2014, 8:49 am{0, 1/15, 1/10, 1/8, 1/6, 3/16, 1/5, 4/17, 3/11, 2/7, 5/16, 6/17, 2/5, 7/17, 3/7, 4/9, 5/11, 1/2, 6/11, 9/16, 7/12, 10/17, 11/17, 2/3, 5/7, 3/4, 13/17, 7/9, 4/5, 9/11, 5/6, 16/19, 7/8, 8/9, 10/11, 11/12, 1, 13/12, 12/11, 15/13, 7/6, 5/4, 9/7, 4/3, 11/8, 3/2, 14/9, 8/5, 13/8, 5/3, 2, 7/3, 5/2, 3, 11/3, 15/4, 4, 13/3, 9/2, 14/3, 5, 6, 8}
Konstantin Knop:
Thank you. Now, N=7.
P=(0,1,2,3,5,12,17), Q=(12,8,5,3,3,3,3). Sum = 12+8+5+3+5+12+17=62.
(30 < 2^5, 62 < 2^6 !)
18 June 2014, 9:26 pmDavid Reynolds:
6 mints
P=(3,3,4,4,3,0) Q=(0,1,1,3,5,10)
total=3+3+4+4+5+10=29
ratios={0/10,1/1,1/2,1/5,2/1,2/5,3/0,3/1,3/2,3/5,3/8,3/10,3/11,4/1,4/3,4/7,4/11,4/13,5/1,5/2,5/3,5/4,5/6,5/7,5/8,5/9,6/1,6/5,6/11,7/1,7/2,7/3,7/4,7/5,7/6,7/8,7/10,7/11,7/12,7/13,7/16,7/18,9/16,10/7,10/9,10/17,10/19,11/4,11/5,11/9,11/14,11/15,11/19,13/7,13/9,13/17,13/19,14/5,14/9,14/15,14/19,17/10,17/20}
7 mints
P=(3,5,6,6,8,6,0) Q=(1,0,3,4,5,10,14)
total=3+5+6+6+8+10+14=52
ratios={0/14,1/1,1/2,1/3,1/4,1/5,2/1,3/1,3/2,3/5,3/7,4/3,4/5,4/7,4/9,5/0,5/2,5/3,5/7,5/8,5/14,6/7,6/17,7/2,7/4,7/5,7/6,7/9,7/11,8/1,8/3,8/5,8/15,8/19,9/4,9/5,9/11,9/19,9/25,10/7,10/9,10/11,10/13,11/3,11/4,11/5,11/6,11/8,11/10,11/12,11/15,11/17,11/18,11/20,11/24,12/7,12/13,13/5,13/9,13/11,13/16,13/18,13/19,14/5,14/9,14/11,14/15,14/17,14/19,14/23,14/25,14/29,15/8,15/14,15/22,15/28,15/29,17/7,17/9,17/10,17/13,17/14,17/16,17/21,17/23,17/24,17/27,17/28,17/30,18/17,18/31,19/8,19/9,19/15,19/22,19/23,19/29,20/19,20/29,20/33,21/32,22/9,22/23,23/13,23/17,23/19,23/20,23/27,23/31,23/33,23/34,25/12,25/18,25/19,25/26,25/32,25/33,28/13,28/19,28/27,28/33,29/23,29/37,31/22,31/36,34/23,34/37}
When all else fails, write code. 😎
21 June 2014, 5:23 pmDavid Reynolds:
Slightly better.
P=(1,2,2,5,5,0) Q=(0,1,2,1,8,10)
total=1+2+2+5+8+10=28
ratios={0/10,1/0,1/1,1/3,1/4,1/6,1/10,2/1,2/3,2/5,2/11,3/1,3/2,3/4,3/5,3/7,3/11,4/1,4/3,4/5,4/7,4/13,5/1,5/2,5/3,5/4,5/7,5/8,5/11,5/13,5/18,6/1,6/5,6/11,7/2,7/3,7/6,7/9,7/10,7/11,7/12,7/13,7/19,7/20,8/3,8/9,8/13,8/19,9/4,9/11,9/14,10/9,10/11,10/19,10/21,11/9,11/19,12/11,13/10,13/11,13/20,13/21,15/22}
P=(2,3,7,2,8,12,0) Q=(0,2,1,7,7,12,12)
total=2+3+7+7+8+12+12=51
ratios={0/12,1/1,1/2,1/3,1/6,2/0,2/1,2/3,2/7,2/19,3/2,3/4,3/14,4/1,4/5,4/7,4/19,5/2,5/7,5/8,5/9,5/13,5/14,5/21,6/5,6/7,6/11,6/13,7/1,7/5,7/6,7/9,7/11,7/12,7/13,8/5,8/7,8/9,8/19,9/1,9/5,9/8,9/11,9/13,9/20,10/3,10/7,10/11,10/19,11/8,11/9,11/13,11/19,11/20,11/21,12/11,12/13,12/17,12/19,13/9,13/11,13/16,13/17,13/21,13/28,14/19,14/31,15/8,15/11,15/14,15/16,15/17,15/26,15/28,16/11,16/17,16/19,16/31,17/8,17/14,17/15,17/20,17/21,17/26,17/27,17/33,19/13,19/15,19/21,19/25,19/27,19/33,20/17,20/19,20/29,20/31,21/13,21/20,21/25,21/32,22/15,22/17,22/19,22/27,22/29,22/31,23/20,23/21,23/32,23/33,25/21,25/28,25/33,27/20,27/28,27/32,27/40,29/20,29/27,29/32,29/39,31/27,31/39,32/29,32/41,34/29,34/41}
I now believe these to be optimal.
24 June 2014, 6:46 amDavid Reynolds:
A note concerning the general lower bound.
24 June 2014, 8:13 amIf r is the number of mints, and r > 1, the number of total coins must be >= ceiling(2^(r/2)).
This is easier to talk about for a discrete case. Let’s take 8 mints as an example.
There are 256 possible outcomes that we must identify with just two weighings, so we must have at least 256 distinct ratios of weight values. For instance, the first weighing might have 20 possible results and the second weighing might only have 13. 20 * 13 > 256. That will work if there aren’t many that reduce to similar ratios. The ideal case, however, would be when the distinct results from both weighing are almost equal. Since the square root of 256 is 16, it is sufficient to have just 16 distinct weight outcomes from each weighing (assuming we can find two sets that have no common ratios). So how many coins do we need to guarantee 16 distinct outcomes?
Let t be the total number of coins.
One outcome is that they are all genuine. weight = t * W(1).
One coin could be fake. weight = (t – 1) * W(1) + W(1 + e).
Two coins could be fake. weight = (t – 2) * W(1) + 2 * W(1 + e).
etc.
We must have at least 15 coins that could be fake to generate 16 distinct outcomes. And this is our minimal answer, 15 total coins.
And now for the second weighing. If we use all the same coins, the ratios will not be unique. If we leave one or more out, we cannot achieve 16 distinct outcomes. Therefore we must add at least 1 more coin to our overall set of coins that we can include in the second weighing. So we must have at least 16 coins, the square root of 2^8.
And in general, that is ceiling(2^(r/2)).
That is more than r, but still very low considering actual results that have been posted. The minimum number of coins to test 6 mints with this formula is 8, but the best case uses 29 coins!
David Reynolds:
8 mints. The exhaustive search is completed.
P=(4,6,6,7,3,13,15,3) Q=(4,0,1,6,12,12,1,27)
total=4+6+6+7+12+13+15+27=90
9 mints seems out of range for an exhaustive search for now.
Here is the best I’ve found so far.
P=(1,2,4,12,5,4,20,39,43) Q=(0,1,3,3,25,33,34,18,27)
29 June 2014, 9:02 amtotal=1+2+4+12+25+33+34+39+43=193
David Reynolds:
A general construction for ApSimon’s mint problem.
Pr = 1, 3, 7, 15, … 2^r-1
Qr = 1, 4, 13, 40, … (3^r-1)/2
Sp(n) = sum(r=1..n, Pr) = 2^(n+1)-n-2
Sq(n) = sum(r=1..n, Qr) = (3^(n+1)-2n-3)/4
Define a function which contains sums of Pr terms in all combinations
fp(1) = P1
fp(2) = P2
fp(3) = P2+P1
fp(4) = P3
fp(5) = P3+P1
fp(6) = P3+P2
fp(7) = P3+P2+P1
fp(8) = P4
…
fp(2^(a-1)) = Pa
fp(2^(a-1)+2^(b-1)) = Pa+Pb
fp(2^(a-1)+2^(b-1)+2^(c-1)+…) = Pa+Pb+Pc+…
fp(2^(a-1)+x) = Pa+fp(x)
For all x != y, fp(x) != fp(y).
All fp values are unique as a consequence of Pr > Sp(r-1).
Construct fq(n) similarly as the sum of Qn terms.
For all x != y, fq(x) != fq(y).
All fq values are unique as a consequence of Qr > Sq(r-1).
f(n)=fp(n)/fq(n)
I will show that for all x != y, f(x) != f(y).
This proves the conditions for a general construction for ApSimon’s mints.
Each new mint r creates 2^n new combinations given by f(2^(n-1)) to f(2^n-1).
Each range has an ascending set of unique values. We just need to show that the
values in each range never overlap.
—– 1 mint —–
f(1) = 1
—– 2 mints —–
f(2) = 0.75
f(3) = 0.8
—– 3 mints —–
f(4) = 0.538462
f(5) = 0.571429
f(6) = 0.588235
f(7) = 0.611111
—– 4 mints —–
f(8) = 0.375
f(9) = 0.390244
f(10) = 0.409091
f(11) = 0.422222
f(12) = 0.415094
f(13) = 0.425926
f(14) = 0.438596
f(15) = 0.448276
—– 5 mints —–
f(16) = 0.256198
f(17) = 0.262295
f(18) = 0.272
f(19) = 0.277778
f(20) = 0.283582
f(21) = 0.288889
f(22) = 0.297101
f(23) = 0.302158
f(24) = 0.285714
f(25) = 0.290123
f(26) = 0.29697
f(27) = 0.301205
f(28) = 0.304598
f(29) = 0.308571
f(30) = 0.314607
f(31) = 0.318436
—– 6 mints —–
f(32) = 0.173077
f(33) = 0.175342
f(34) = 0.179348
f(35) = 0.181572
f(36) = 0.185676
f(37) = 0.187831
f(38) = 0.191601
f(39) = 0.193717
f(40) = 0.193069
f(41) = 0.195062
f(42) = 0.198529
f(43) = 0.200489
f(44) = 0.203837
f(45) = 0.205742
f(46) = 0.209026
f(47) = 0.2109
f(48) = 0.193814
f(49) = 0.195473
f(50) = 0.198364
f(51) = 0.2
f(52) = 0.202811
f(53) = 0.204409
f(54) = 0.207171
f(55) = 0.208748
f(56) = 0.207619
f(57) = 0.209125
f(58) = 0.21172
f(59) = 0.213208
f(60) = 0.215613
f(61) = 0.217069
f(62) = 0.219557
f(63) = 0.220994
We need to show that f(2^n-1) f(2^(n+2)-1) for all n.
If that is the case, the ranges never overlap and all values of f(x) are unique.
f(2^(n-1)) = fp(2^(n-1))/fq(2^(n-1)) = Pn/Qn = (2^n-1)/((3^n-1)/2) = (2^(n+1)-2)/(3^n-1)
f(2^(n-2)) = (2^n-2)/(3^(n-1)-1)
fp(2^n-1) = fp(2^(n-1)+2^(n-2)+2^(n-2)+2^(n-1)+…1) = Pn + Pn-1 + Pn-2 + … P1 = Sp(n) = 2^(n+1)-n-2
fq(2^n-1) = Sq(n) = (3^(n+1)-2n-3)/4
f(2^n-1) = fp(2^n-1)/fq(2^n-1) = (2^(n+1)-n-2)/((3^(n+1)-2n-3)/4) = (2^(n+3)-4n-8)/(3^(n+1)-2n-3)
f(2^(n+2)-1) = (2^(n+5)-4n-16)/(3^(n+3)-2n-7)
f(2^n-1) < f(2^(n-2))
(2^(n+3)-4n-8)/(3^(n+1)-2n-3) < (2^n-2)/(3^(n-1)-1)
(2^(n+3)-4n-8)*(3^(n-1)-1) < (2^n-2)*(3^(n+1)-2n-3)
O(2^(n+3)*3^(n-1)) < O((2^n)*3^(n+1))
divide both sides by 2^n*3^(n-1)
8 f(2^(n+2)-1)
(2^(n+1)-2)/(3^n-1) > (2^(n+5)-4n-16)/(3^(n+3)-2n-7)
(2^(n+1)-2)*(3^(n+3)-2n-7) > (2^(n+5)-4n-16)*(3^n-1)
O(2^(n+1)*3^(n+3)) > O(2^(n+5)*3^n)
divide both sides by 2^(n+1)*3^n
27 > 16
The second assertion holds for all n larger than 0.
The general construction therefore holds for any number of mints and we have reduced the upper bound for n mints to (3^(n+1)-2n-3)/4.
3 July 2014, 4:04 pmDavid Reynolds:
Somehow this statement got corrupted in the last post.
We need to show that f(2^n-1) f(2^(n+2)-1) for all n.
3 July 2014, 4:06 pmIf that is the case, the ranges never overlap and all values of f(x) are unique.
David Reynolds:
Okay, it just won’t show correctly.
Let me try a more verbose tactic.
We need to show that f(2^n-1) is less than f(2^(n-2))
3 July 2014, 4:08 pmAND
f(2^(n-1)) is greater than f(2^(n+2)-1).
David Reynolds:
I noticed that other statements near the end were also corrupted. Let me try them again.
f(2^n-1) < f(2^(n-2))
(2^(n+3)-4n-8)/(3^(n+1)-2n-3) < (2^n-2)/(3^(n-1)-1)
(2^(n+3)-4n-8)*(3^(n-1)-1) < (2^n-2)*(3^(n+1)-2n-3)
O(2^(n+3)*3^(n-1)) < O((2^n)*3^(n+1))
divide both sides by 2^n*3^(n-1)
8 f(2^(n+2)-1)
(2^(n+1)-2)/(3^n-1) > (2^(n+5)-4n-16)/(3^(n+3)-2n-7)
(2^(n+1)-2)*(3^(n+3)-2n-7) > (2^(n+5)-4n-16)*(3^n-1)
O(2^(n+1)*3^(n+3)) > O(2^(n+5)*3^n)
divide both sides by 2^(n+1)*3^n
27 > 16
The second assertion holds for all n larger than 0.
3 July 2014, 4:12 pmDavid Reynolds:
Hmmm… There is a proof here, honest.
I’ll remove all less than and greater than signs and post again.
f(2^n-1) is less than f(2^(n-2))
(2^(n+3)-4n-8)/(3^(n+1)-2n-3) is less than (2^n-2)/(3^(n-1)-1)
(2^(n+3)-4n-8)*(3^(n-1)-1) is less than (2^n-2)*(3^(n+1)-2n-3)
O(2^(n+3)*3^(n-1)) is less than O((2^n)*3^(n+1))
divide both sides by 2^n*3^(n-1)
8 is less than 9
The first assertion holds all n larger than 1.
f(2^(n-1)) is greater than f(2^(n+2)-1)
(2^(n+1)-2)/(3^n-1) is greater than (2^(n+5)-4n-16)/(3^(n+3)-2n-7)
(2^(n+1)-2)*(3^(n+3)-2n-7) is greater than (2^(n+5)-4n-16)*(3^n-1)
O(2^(n+1)*3^(n+3)) is greater than O(2^(n+5)*3^n)
divide both sides by 2^(n+1)*3^n
27 is greater than 16
The second assertion holds for all n larger than 0.
3 July 2014, 4:14 pmDavid Reynolds:
Okay. It’s now showing correctly in my browser (Mozilla Firefox).
3 July 2014, 4:16 pmThings were dropped out when I had less than and greater than symbols in the text.
David Reynolds:
Concerning my general construction for ApSimon’s mints…
My reasoning for the technique to work for any arbitrary number of mints is that the ratios produced are all unique.
4 July 2014, 5:54 pmEach mint creates a range of ascending, unique ratios, and no two ranges can overlap.
I am confident that the ranges will never overlap.
However, the ranges aren’t strictly ascending.
This is evident even from the results I posted, starting at just 4 mints.
This raises the possibility that, given enough mints, a ratio may be duplicated within a single range.
I have verified my general construction for up to 25 mints and no duplication has appeared.
But infinity is very large and I must therefore retract my “proof”.
Richard J. Mathar:
The preprint arXiv:1407.3613 considers the problem if more than two weighings are allowed.
9 October 2014, 10:31 amOnly numerical results are demonstrated, obtained by brute force enumerations.